package alogrithm.solution;

import java.util.Stack;

import alogrithm.structure.TreeNode;

/*
 * 第16题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。   
例如输入
  8
  / \
 6 10
/ \ / \
5 7 9 11

输出8 6 10 5 7 9 11。

 */
public class P16 {
	public static void printTreeByLevel(TreeNode node)
	{
		if(node==null)return;
		Stack<TreeNode> s=new Stack<TreeNode>();
		Stack<TreeNode> s_copy=new Stack<TreeNode>();
		s_copy.push(node);
		while(!s_copy.isEmpty())
		{
			while(!s_copy.isEmpty())
				s.push(s_copy.pop());
			while(!s.isEmpty())
			{
				TreeNode tmp=s.pop();
				System.out.print(tmp.getValue()+"\t");
				if(tmp.getLeftChild()!=null)
					s_copy.push(tmp.getLeftChild());
				if(tmp.getRightChild()!=null)
					s_copy.push(tmp.getRightChild());
			}
			System.out.println();
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode n1=new TreeNode(4);
		TreeNode n2=new TreeNode(8);
		TreeNode n3=new TreeNode(12);
		TreeNode n4=new TreeNode(16);
		TreeNode n5=new TreeNode(6,n1,n2);
		TreeNode n6=new TreeNode(14,n3,n4);
		TreeNode n7=new TreeNode(10,n5,n6);
		printTreeByLevel(n7);

	}

}
